package com.atwy.linearstructure.linkedList;

import java.util.Stack;

/**
 * 单向链表的案例
 */
public class SingleLinkedListDemo {

    public static void main(String[] args) {
        // 先创建节点
        HeroNode node1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode node2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode node3 = new HeroNode(3, "吴用", "智多星");
        HeroNode node4 = new HeroNode(6, "林冲", "豹子头");
        HeroNode node5 = new HeroNode(5, "关胜", "大刀");
        // 无序进行添加
        SingleLinkedList list01 = new SingleLinkedList();
        list01.add(node1);
        list01.add(node4);
        list01.add(node3);
        list01.add(node2);
        list01.add(node5);
        // 打印数据
        System.out.println("打印无序的链表数据start");
        list01.list();
        System.out.println("打印无序的链表数据end");

        // 有序添加
        // 先创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(6, "林冲", "豹子头");
        HeroNode heroNode5 = new HeroNode(5, "关胜", "大刀");

        System.out.println("有序添加开始~");
        SingleLinkedList list02 = new SingleLinkedList();
        list02.addByOrder(heroNode3);
        list02.addByOrder(heroNode1);
        list02.addByOrder(heroNode4);
        list02.addByOrder(heroNode2);
        list02.addByOrder(heroNode5);
        System.out.println("打印有序的链表数据start");
        list02.list();
        System.out.println("打印有序的链表数据end");

        System.out.println("对list01进行操作");
        list01.update(new HeroNode(1, "松江", "呼保义"));
        list01.delete(3);
        list01.list();

        System.out.println("对list02进行操作");
        list02.update(new HeroNode(1, "松江", "呼保义"));
        list02.delete(3);
        list02.delete(2);
        list02.list();
        System.out.println("###################");

        // 面试题
        // 1、求单链表中有效节点的个数
        System.out.println("list01的有效节点数：" + list01.getLength());
        System.out.println("list02的有效节点数：" + list02.getLength());
        System.out.println("###################");

        // 2、查找单链表中的倒数第 k 个结点
        System.out.printf("list01倒数第二个是%s\n", list01.getLast(2));
        System.out.printf("list02倒数第二个是%s\n", list02.getLast(2));
        System.out.printf("list01倒数第二个是%s\n", list01.getLast(3));
        System.out.printf("list02倒数第二个是%s\n", list02.getLast(4));
        System.out.println("###################");

        // 3、单链表的反转
        System.out.println("list01逆转之前：");
        list01.list();
        list01.reverse();
        System.out.println("list01逆转之后：");
        list01.list();

        System.out.println("list02逆转之前：");
        list02.list();
        list02.reverse();
        System.out.println("list02逆转之后：");
        list02.list();
        System.out.println("###################");

        // 4、从尾到头打印单链表
        // 利用链表的反转？不建议，因为会破坏原链表结构
        // 可以使用栈实现
        System.out.println("逆序打印list01:");
        list01.reversePrint();
        System.out.println("没有破坏list01的结构，不信你看：");
        list01.list();
        System.out.println("###################");

        // 5、合并两个有序的单链表，合并之后的链表依然有序
        // 先创建节点
        HeroNode n1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode n2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode n3 = new HeroNode(3, "吴用", "智多星");

        HeroNode m1 = new HeroNode(6, "林冲", "豹子头");
        HeroNode m2 = new HeroNode(5, "关胜", "大刀");
        HeroNode m3 = new HeroNode(2, "卢俊义", "玉麒麟");

        SingleLinkedList list03 = new SingleLinkedList();
        SingleLinkedList list04 = new SingleLinkedList();
        list03.addByOrder(n1);
        list03.addByOrder(n2);
        list03.addByOrder(n3);
        System.out.println("list03:");
        list03.list();

        list04.addByOrder(m1);
        list04.addByOrder(m2);
        list04.addByOrder(m3);
        System.out.println("list04:");
        list04.list();

        System.out.println("按顺序合并~");
        list04.mergebyOrder(list03);
        list04.list();

        System.out.println("======================================");
        HeroNode h1 = new HeroNode(8, "宋江", "及时雨");
        HeroNode h2 = new HeroNode(6, "卢俊义", "玉麒麟");
        HeroNode h3 = new HeroNode(3, "吴用", "智多星");

        HeroNode hh1 = new HeroNode(6, "林冲", "豹子头");
        HeroNode hh2 = new HeroNode(9, "关胜", "大刀");
        HeroNode hh3 = new HeroNode(4, "卢俊义", "玉麒麟");

        SingleLinkedList list05 = new SingleLinkedList();
        SingleLinkedList list06 = new SingleLinkedList();

        list05.addByOrder(h1);
        list05.addByOrder(h3);
        list05.addByOrder(h2);

        list06.addByOrder(hh1);
        list06.addByOrder(hh2);
        list06.addByOrder(hh3);
        System.out.println("链表1：");
        list05.list();

        System.out.println("-------");
        System.out.println("链表2：");
        list06.list();

        list05.mergeByOrderQuikly(list06);

        System.out.println("合并之后：");
        list05.list();
    }
}

/**
 * 链表：
 * 1、链表是以节点的方式来存储,是链式存储
 * 2、每个节点包含 data 域， next 域：指向下一个节点
 * 3、链表分带头节点的链表和没有头节点的链表（本例是带头节点的）
 * 4、使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作
 * 5.1、第一种方法在添加英雄时，直接添加到链表的尾部
 * <p>
 * 5.2、第二种方法增加时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)
 */
class SingleLinkedList {
    /**
     * 预定义一个头节点，头节点不要动, 不存放具体的数据
     */
    private HeroNode headHeroNode = new HeroNode(0, "", "");

    /**
     * 不考虑排序进行插入。
     * 从头节点开始遍历，当节点的next为null时，表示到达链表的尾部。
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        if (heroNode == null) {
            return;
        }
        // 因为 head 节点不能动，因此需要一个辅助遍历 temp
        HeroNode temp = headHeroNode;
        while (true) {
            // 找到链表的最后
            if (temp.next == null) {
                break;
            }
            // 没到最后，将temp后移
            temp = temp.next;
        }
        /*while (temp.next != null) {
            temp = temp.next;
        }*/

        // 当退出 while 循环时，temp 就指向了链表的最后
        // 将最后这个节点的 next 指向 新的节点
        temp.next = heroNode;
    }

    /**
     * 根据排名进行插入。
     * 从头节点开始遍历，temp指向当前节点，取出temp.next的数据进行比较，满足就跳出循环
     * 将新节点next指向temp.next，temp的next指向新节点
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        if (heroNode == null) {
            return;
        }
        HeroNode temp = headHeroNode;
        // flag 标志添加的编号是否存在，默认为 false
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                // 说明到链表的最后了
                break;
            }
            if (heroNode.heroNo < temp.next.heroNo) {
                // 说明当前temp是目标，新节点可以添加到temp后面
                break;
            } else if (heroNode.heroNo == temp.next.heroNo) {
                flag = true;
                break;
            }
            // 后移
            temp = temp.next;
        }
        if (flag) {
            System.out.printf("英雄编号%d，已存在\n", heroNode.heroNo);
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

        /*while (temp.next != null) {
            if (heroNode.heroNo < temp.next.heroNo) {
                // 说明当前temp是目标
                break;
            } else if (heroNode.heroNo == temp.next.heroNo) {
                throw new RuntimeException("排名重复~");
            }
            temp = temp.next;
        }
        heroNode.next = temp.next;
        temp.next = heroNode;*/
    }

    /**
     * 按排名进行删除。
     * 先遍历找到节点
     *
     * @param no
     */
    public void delete(int no) {
        HeroNode temp = headHeroNode;
        while (temp.next != null) {
            if (no == temp.next.heroNo) {
                break;
            }
            temp = temp.next;
        }
        if (temp.next == null) {
            // 说明没找到
            return;
        }
        temp.next = temp.next.next;
    }


    /**
     * 按照排名进行更新信息
     * 根据排名找到相应的节点，遍历
     *
     * @param heroNode
     */
    public void update(HeroNode heroNode) {
        if (heroNode == null) {
            return;
        }
        HeroNode temp = headHeroNode;
        while (temp.next != null) {
            if (heroNode.heroNo == temp.next.heroNo) {
                break;
            }
            temp = temp.next;
        }
        if (temp.next == null) {
            // 说明没找到
            return;
        }
        temp.next.name = heroNode.name;
        temp.next.nickName = heroNode.nickName;
    }

    /**
     * 打印链表数据
     */
    public void list() {
        HeroNode temp = headHeroNode;
        while (temp.next != null) {
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

    /**
     * 返回链表中节点数,不包含头结点
     *
     * @return
     */
    public int getLength() {
        int length = 0;
        HeroNode temp = headHeroNode;
        while (true) {
            if (temp.next == null) {
                // 说明该节点是最后一个
                break;
            }
            length++;
            temp = temp.next;
        }

        return length;
    }

    /**
     * 查找单链表中的倒数第 k 个节点。
     * 1、先遍历得到有效节点数length
     * 2、再次遍历得到length-k位置的节点,
     * 3、利用临时节点temp，当该节点指向从第一个有效节点（头节点的下一个节点）开始时
     * 往后移动length-k即可得到目标节点。
     * <p>
     * 没找到返回null
     *
     * @param lastIndex:倒数第 k 个节点
     * @return
     */
    public HeroNode getLast(int lastIndex) {
        int length = getLength();
        if (lastIndex > length || lastIndex < 0) {
            return null;
        }
        if (headHeroNode.next == null) {
            return null;
        }
        HeroNode temp = headHeroNode.next;// 总共3个，倒数第2个，3-2=1
        for (int i = 0; i < length - lastIndex; i++) {
            temp = temp.next;
        }

        return temp;
    }

    /**
     * 单链表的反转。（双指针 + 头插法）
     * 1、构建新链表，新链表采用头插法。
     * 2、原链表需要双指针遍历，
     * 2.1当前节点curr一个指针，
     * 2.2当前节点的下一个节点next一个指针。
     * 3、新链表头插法：
     * 3.1新加入的节点curr指向新链表头节点 newHead 的下一个节点curr->newHead.next
     * 3.2新链表头节点指向新加入的节点 newHead.next->curr
     * 4、链表curr后移
     * 5、旧链表的头节点指向构建好的链表
     */
    public void reverse() {
        if (headHeroNode.next == null) {
            return;
        }
        // 构建新链表，
        HeroNode newHead = new HeroNode(0, "", "");

        HeroNode curr = headHeroNode.next;
        HeroNode next = null;

        while (true) {
            if (curr == null) {
                // 节点到最后了
                break;
            }
            //记录当前节点的下一个位置
            next = curr.next;

            // 另一条链表头插法完成连接
            curr.next = newHead.next;// 新加入的节点next指向新链表头节点的下一个节点
            newHead.next = curr;// 新链表头节点指向新加入的节点

            // 原链表进行后移
            curr = next;
        }
        // 将原链表头 指向新链表头后面的节点
        headHeroNode.next = newHead.next;
    }

    /**
     * 返回头结点
     *
     * @return
     */
    public HeroNode peek() {
        return headHeroNode;
    }

    /**
     * 合并两个有序的单链表，合并之后的链表依然有序
     * 这里要确保本链表是有顺序的
     * 1、遍历新加入的链表，得到每个节点，将其按顺序插入本链表
     * 2、遍历时注意 curr当前节点 和 next记录当前节点的下一个节点（双指针）
     *
     * @param antherList
     */
    public void mergebyOrder(SingleLinkedList antherList) {
        if (antherList == null || antherList.getLength() == 0) {
            return;
        }
        HeroNode head = antherList.peek();
        HeroNode curr = head.next;
        HeroNode next = null;
        while (true) {
            if (curr == null) {
                break;
            }
            // 记录下一个位置，因为添加到另一链表时会破坏下一个指向
            next = curr.next;
            // 按顺序添加
            this.addByOrder(curr);
            // temp向后移动
            curr = next;
        }
    }

    /**
     * 将两个有序链表合并，合并之后的链表仍是有序的
     * 优化版：
     * 思路，两个链表本来就是有序的，添加时可以利用这个点来减少遍历次数
     *
     *
     * @param antherList
     */
    public void mergeByOrderQuikly(SingleLinkedList antherList) {
        if (antherList == null || antherList.getLength() == 0) {
            return;
        }
        // 链表2的节点一定添加在pre和temp之间
        HeroNode pre = headHeroNode;
        HeroNode current = pre.next;

        // head2:链表2的头节点，头节点的编号为0，最小的
        HeroNode head2 = antherList.peek();

        // slow从头节点开始，总是小于current
        HeroNode slow = head2;
        // fast从第一个有效节点开始，当fast < current时，slow、fast后移，fast > current,pre、current后移
        HeroNode fast = slow.next;
        // 当 fast > current,pre<slow<current时，就可以把链表2的部分截取（head,slow]添加至pre-current之间
        // flag为ture说明需要进行截取-添加了
        boolean flag = false;

        // 排序时从小到大的
        while (true) {
            if (current == null) {
                pre.next = fast;
                break;
            }
            if (fast == null) {
                // 此时slow一定小于temp
                slow.next = current;
                pre.next = head2.next;
                break;
            }
            if (fast.heroNo < current.heroNo) {
                // 链表2小于链表1的节点时，链表2后移
                slow = slow.next;
                fast = fast.next;
            } else if (fast.heroNo > current.heroNo) {
                if (slow.heroNo < current.heroNo && slow.heroNo > pre.heroNo) {
                    flag = true;
                } else {
                    flag = false;
                    // 后移
                    pre = current;
                    current = current.next;
                }
            }else if(fast.heroNo == current.heroNo){// 相等的时候跳过不插入
                // 链表2的指针slow重置到head2
                HeroNode end = slow;
                slow = head2;

                // 解放链表1的pre
                HeroNode preTemp = pre;

                // 将head2至end的节点连接到链表1上，包尾不包头
                end.next = current;
                preTemp.next = head2.next;

                // 链表1后移
                pre = current;
                current = current.next;

                // 链表2的fast后移
                fast = fast.next;
                // head2连接到新fast上
                slow.next = fast;
            }
            if (flag) {// 需要截取-添加
                // 链表2的指针slow重置到head2
                HeroNode end = slow;
                slow = head2;

                // 解放链表1的pre
                HeroNode preTemp = pre;

                // 将head2至end的节点连接到链表1上，包尾不包头
                end.next = current;
                preTemp.next = head2.next;

                // 链表1后移
                pre = current;
                current = current.next;

                flag = false;
            }


        }
    }

    /**
     * 逆序打印，不破坏结构
     */
    public void reversePrint() {
        Stack<HeroNode> stack = new Stack<>();
        HeroNode curr = headHeroNode.next;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }
        //将栈中的节点进行打印,pop 出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
}


/**
 * 链表的节点：
 * data域
 * next域
 */
class HeroNode {
    /**
     * data域
     */
    int heroNo;
    String name;
    String nickName;

    /**
     * next域
     */
    HeroNode next;

    public HeroNode(int heroNo, String name, String nickName) {
        this.heroNo = heroNo;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("HeroNode{");
        sb.append("heroNo=").append(heroNo);
        sb.append(", name='").append(name).append('\'');
        sb.append(", nickName='").append(nickName).append('\'');
        sb.append('}');
        return sb.toString();
    }
}